package binary_tree.leetcode;

/**
 * 从前序与中序遍历序列构造二叉树
 * @Author Stark
 * @Date 2022/3/1 16:15
 */
public class Num105_BuildTreeByPreAndIn {
    //记录前序遍历的下标
    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(0,preorder.length - 1,preorder,inorder);
    }
    private TreeNode buildTreeHelper(int left,int right,int[] preorder,int[] inorder){
        //如果left大于right说明该结点不存在,或者前序遍历完了就返回null
        if(left > right || index >= preorder.length){
            return null;
        }
        //获取前序遍历的值并创建新结点
        int num = preorder[index++];
        TreeNode node = new TreeNode(num);
        //在中序遍历中找到该结点的位置
        int inSub = find(num,inorder);
        //递归拼接二叉树
        node.left = buildTreeHelper(left,inSub - 1,preorder,inorder);
        node.right = buildTreeHelper(inSub + 1,right,preorder,inorder);
        return node;
    }
    //在中序遍历中找到该结点的下标
    private int find(int num, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i] == num){
                return i;
            }
        }
        return -1;
    }
}
